#include <stdio.h>
#include <string.h>

#define INF 0x3f3f3f
#define MAXV 4

/**
 * Floyd算法
 * 求每对顶点之间的最短路径
 * 也称多源最短路径算法
 */

typedef struct Graph
{
    int n;
    int edges[MAXV][MAXV];
} Graph;

/**
 * 打印所有最短路径
 */
void printAllPath(Graph g, int A[][MAXV], int path[][MAXV])
{
    int i, j;           // 用于遍历矩阵A
    int k;              // 用于记录前驱节点
    int apath[MAXV], d; // 用于存储一条最短路径

    for (i = 0; i < g.n; i++)
    {
        for (j = 0; j < g.n; j++)
        {
            if (i != j && A[i][j] < INF)
            {
                printf("from %d to %d min distance : %d \t path: ", i, j, A[i][j]);
                // 添加终点
                d = 0;
                apath[d] = j;
                // 获取前驱节点
                k = path[i][j];
                // 一直找到起点
                while (k != i)
                {
                    d++;
                    apath[d] = k;
                    k = path[i][k];
                }
                // 添加起点
                d++;
                apath[d] = i;

                // 输出起点
                printf("%d", apath[d]);
                // 递归的输出路径
                for (int s = d-1; s>=0; s--)
                {
                    printf("->%d", apath[s]);
                }
                printf("\n");
            }
        }
    }
}

// Floyd
void floyd(Graph g)
{
    int A[MAXV][MAXV];    // 存储每两个节点间的最短路径
    int path[MAXV][MAXV]; // 存储最短路径的前驱节点，如path[i][j] = k 表示从i到j的最短路径，j的前驱节点为k

    int i, j; // 用于遍历图的邻接矩阵
    int k;    // 用户标记循环处理的节点

    // 初始化
    for (i = 0; i < g.n; i++)
    {
        for (j = 0; j < g.n; j++)
        {
            A[i][j] = g.edges[i][j];
            if (i != j && A[i][j] < INF)
            {
                path[i][j] = i;
            }
            else
            {
                path[i][j] = -1;
            }
        }
    }

    for (k = 0; k < g.n; k++)
    {
        // 依次添加节点0到n-1，处理A及path
        for (i = 0; i < g.n; i++)
        {
            for (j = 0; j < g.n; j++)
            {
                if (A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }
    printAllPath(g, A, path);
}

// 构建无向图
void createGraph(Graph *g)
{
    int i, j;
    g->n = MAXV;
    int adjMatrix[MAXV][MAXV] = {
        {0, 5, INF, 7},
        {INF, 0, 4, 2},
        {3, 3, 0, 2},
        {INF, INF, 1, 0}};
    for (i = 0; i < MAXV; i++)
    {
        for (j = 0; j < MAXV; j++)
        {
            g->edges[i][j] = adjMatrix[i][j];
        }
    }
}

int main()
{
    Graph g;
    createGraph(&g);
    floyd(g);
    return 0;
}
